package 剑指Offer;

public class Offer56II_数组中数字出现的次数II {
    public static void main(String[] args) {
        new Offer56II_数组中数字出现的次数II().singleNumber(new int[]{3, 4, 3, 3});
    }

    public int singleNumber(int[] nums) {
        if (nums.length == 0) {
            return -1;
        }
        //java int类型有32位，其中首位为符号位：用于记录 数组中所有数字 的 每一位的和
        int[] bitSum = new int[32];
        int res = 0;

        for (int num : nums) {
            //二进制数为0001，方便确定num的哪一位是1，要放在这里，每次循环开始都要初始化
            int curBit = 1;
            /*
                由高到低，遍历当前数字的每一位，
                若 当前位为1，则使bitSumArray数组的相应的单元的值+1
            */
            for (int i = 31; i >= 0; i--) {
                if ((curBit & num) != 0) {
                    bitSum[i] = bitSum[i] + 1;
                }
                curBit <<= 1;
            }
        }
        /*遍历bitSum数组的每一位，取每一位和3取余的结果（肯定为0或1）
        并将其 加入到 结果result的适当位上*/
        for (int i = 0; i < 32; i++) {
            res = res << 1;
            res = res + bitSum[i] % 3;//这两步顺序不能变，否则最后一步会多左移一次
        }

        return res;
    }
}
